package 二叉树;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class NC16判断二叉树是否对称 {

    /**
     * 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
     * 例如：下面这棵二叉树是对称的
     *      1
     *     /  \
     *   2    2
     *  / \    / \
     * 3 4  4  3
     * 下面这棵二叉树不对称。
     *     1
     *     / \
     *   2   2
     *     \    \
     *     3    3
     * 备注：
     * 希望你可以用递归和迭代两种方法解决这个问题
     */

    //不要队列存储元素去解,是错的,因为两边的叶子节点不能判断是否在同一边
    public boolean isSymmetric (TreeNode root) {

        if(root==null){
            return true;
        }

        return dfs(root.left,root.right);

    }

    private boolean dfs(TreeNode node1,TreeNode node2){
        if(node1==null&&node2==null){
            return true;
        }
        if(node1==null||node2==null){
            return false;
        }
        if(node1.val!=node2.val){
            return false;
        }
        return dfs(node1.left,node2.right)&&dfs(node1.right,node2.left);
    }

    //采用非递归解法
    public boolean isSymmetric2 (TreeNode root) {

        if(root==null){
            return true;
        }

        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.addLast(root);
        queue.addLast(root);


        while (!queue.isEmpty()){

            TreeNode node1 = queue.pollFirst();
            TreeNode node2 = queue.pollFirst();

            if(node1==null&&node2==null){
                continue;
            }
            if((node1==null||node2==null)||(node1.val!=node2.val)){
                return false;
            }

            queue.offerLast(node1.left);
            queue.addLast(node2.right);

            queue.addLast(node1.right);
            queue.addLast(node2.left);

        }

        return true;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{1,2,2,3,4,4,3});
        NC16判断二叉树是否对称 n=new NC16判断二叉树是否对称();
        boolean result = n.isSymmetric2(treeNode);
        System.out.println(result);
    }

}
